#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

#if 0
int min = 15;
int total = 15;
int sum = 0;

// 给定一个数组，找出子数组与另一个子数组的和的差值最小
void fun(int *arr, int idx, int len, int *x, vector<vector<int>> &temp)
{
    if(idx == len){
        int fir{}, sec{};   

        if(sum == 0 || sum == total) return;
        if(abs(total - sum - sum) < min){
            min = abs(total - sum - sum);
            vector<int> firV, secV;
            for(size_t i{}; i < len; i++){
                if(x[i])    
                    firV.push_back(arr[i]);
                else
                    secV.push_back(arr[i]);
            }

            temp.clear();
            temp.push_back(firV);
            temp.push_back(secV);
        }
    }else{
        sum += arr[idx];
        x[idx] = 1;
        fun(arr, idx + 1, len, x, temp);

        sum -= arr[idx];
        x[idx] = 0;
        fun(arr, idx + 1, len, x, temp);
    }
}

#endif

vector<int> tmpVec, bestVec;
size_t min = -1, sum{}, total{};

void fun(int *arr, int idx, int len)
{

    if(idx == len){
        int remain = total - sum;
        if(abs(remain - sum) < min){
            min = abs(remain - sum);

            bestVec = tmpVec;
        }
    }else{

        // 记录状态
        sum += arr[idx];
        tmpVec.push_back(arr[idx]);
        fun(arr, idx + 1, len);

        // 回溯
        sum -= arr[idx];
        tmpVec.pop_back();
        fun(arr, idx + 1, len);
    }
}

void test()
{

    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(int);

    for(size_t i{}; i < len; i++){
        total += arr[i];
    }

    fun(arr, 0, len);

    for(int i: bestVec){
        printf("%d ", i);
    }
    printf(", min: %d\n", min);


    #if 0
    int arr[] = {1, 2, 3, 4, 5};
    int len = sizeof(arr) / sizeof(int);
    int x[len] = {0};
    vector<vector<int>> vec;

    fun(arr, 0, len, x, vec);

    for(const vector<int> vecs: vec){
        for(int i: vecs){
            printf("%d ", i);
        }
        printf("\n");
    }
    #endif

}

int main(int args, char *argv[])
{
    test();
    return 0;
}